For the design of digital circuits on the scale of VLSI (very large scale integration) technology, designers often employ computer-aided techniques. Standard languages such as Hardware Description Languages (HDLs) have been developed to describe digital circuits to aide in the design and simulation of complex digital circuits. Several hardware description languages, such as VHDL and Verilog, have evolved as industry standards. VHDL and Verilog are general purpose hardware description languages that allow definition of a hardware model at the gate level, the register transfer level (RTL) or the behavioral level using abstract data types. As device technology continues to advance, various product design tools have been developed to adapt HDLs for use with newer devices and design styles.
In designing an integrated circuit with an HDL code, the code is first written and then compiled by an HDL compiler. The HDL source code describes at some level the circuit elements, and the compiler produces an RTL netlist from this compilation. The RTL netlist is typically a technology independent netlist in that it is independent of the technology/architecture of a specific vendor's integrated circuit, such as field programmable gate arrays (FPGA) or an application-specific integrated circuit (ASIC). The RTL netlist corresponds to a schematic representation of circuit elements (as opposed to a behavioral representation). A mapping operation is then performed to convert from the technology independent RTL netlist to a technology specific netlist which can be used to create circuits in the vendor's technology/architecture. It is well known that FPGA vendors utilize different technologies/architectures to implement logic circuits within their integrated circuits. Thus, the technology independent RTL netlist is mapped to create a netlist which is specific to a particular vendor's technology/architecture.
One operation which is often desirable in this process is to plan the layout of a particular integrated circuit and to control timing problems and to manage interconnections between regions of an integrated circuit. This is sometimes referred to as “floor planning.” A typical floor planning operation divides the circuit area of an integrated circuit into regions, sometimes called “blocks,” and then assigns logic to reside in a block. These regions may be rectangular or non-rectangular. This operation has two effects: the estimation error for the location of the logic is reduced from the size of the integrated circuit to the size of the block (which tends to reduce errors in timing estimates), and the placement and the routing typically runs faster because as it has been reduced from one very large problem into a series of simpler problems.
After the logic elements are placed into blocks, the cells (e.g., gates or transistors) are placed and routed in the area for a chip. FIG. 2 shows a conventional method to place and route the cells of an integrated circuit. After operation 201 places all cells for the integrated circuit, operation 203 routes wires between cells. Thus, the operations of placing and routing are separated. Since the placement is performed without actual routing, the placement of the cells is based on the estimated routing. Once the wires are actually routed, operation 205 can analyze timing accurately based on the placement and routing information. If operation 207 determines that the timing requirements (e.g., slack) are not satisfied, the previous design may be modified in operation 209, before the cells are placed again in operation 201.
Slack is the difference between the desired delay and the actual (estimated or computed) delay. When the desired delay is larger than the actual delay, the slack is positive; otherwise, the slack is negative. Typically, it is necessary to make the slack positive (or close to zero) to meet the timing requirement (e.g., reducing the wire delay to increase the slack).
Thus, the conventional method separates the phases of placement and routing. The cells (e.g., gates) of a design are fully placed (e.g., assigned locations) before the wires are actually routed. Multiple iterations of this process may be applied but the design is typically still fully placed before routing is assigned (or reassigned).
Because the wires are not routed at the same time as placement, conventional placement algorithms estimate the result of routing. These estimates do not account for the available information of routed wires, even if only a small part of an already placed and routed design is being modified.